
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next

class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next

print("合并两个有序链表"
      "将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的")
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
def hebingyouxulianbiao(list1:ListNode,list2:ListNode)->ListNode:
    if not list1 and not list2:
        return None
    if not list1:
        return list2
    if not list2:
        return list1
    new_head=ListNode()
    current=new_head
    while list1 and list2:
        if list1.val<=list2.val:
            current.next=list1
            list1=list1.next
        else:
            current.next=list2
            list2=list2.next
        current=current.next
    if not list1:
        current.next=list2
    if not list2:
        current.next=list1
    return new_head.next

print("数组元素加1")
def shuzuyuansujia1(digits:list[int])->list[int]:
    cp_digits=[0]*len(digits)
    cp_digits[-1]=1
    index_1,index_2,jinwei=len(digits)-1,len(digits)-1,0
    res_list=[]
    while index_1>=0:
        tem=digits[index_1]+cp_digits[index_2]+jinwei
        res_list.insert(tem%10)
        jinwei=tem//10
        index_1-=1
        index_2-=1





print("X的算数平方根"
      "给你一个非负整数 x,由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去")
def suanshupingfanggen(x:int)->int:
    if x<=1:
        return x
    for i in range(1,x+1):
        if i**2==x:
            return i
        if (i+1)**2>x:
            return i

print("爬楼梯")
def palouti(n:int)->int:
    if n==0 or n==1:
        return 1
    return palouti(n-1)+palouti(n-2)
def palouti2(n:int)->int:
    res=[1,2]
    if n<=2:
        return res[n-1]
    while len(res)<n:
        res.append(res[-1]+res[-2])
    return res[-1]

print("删除排序链表中的重复元素")
def shanchuchongfuyuansu(head:ListNode)->ListNode:
    if not head:
        return None
    current=head
    while current.next:
        if current.val==current.next.val:
            current.next=current.next.next
        else:
            current=current.next
    return head


print("合并两个有序数组"
      "请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。"
      "注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，"
      "其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n")
def merge(nums1:list[int],m:int,nums2:list[int],n:int)->list[int]:
    nums1[m:]=nums2
    nums1.sort()



print("判断是不是相同的树")
def isSameTree(p:TreeNode,q:TreeNode):
    if not p and not q:
        return True
    if not p or not q:
        return False
    return p.val==q.val and isSameTree(p.left,q.left) and isSameTree(p.right,q.right)

print("判断是不是对称二叉树")
def isSymmetric(root:TreeNode)->bool:
    def inner(left:TreeNode,right:TreeNode):
        if not left and not right:
            return True
        if not left or not right or left.val!=right.val:
            return False
        return inner(left.left,right.right) and inner(left.right,right.left)
    if not root:
        return False
    else:
        return inner(root.left,root.right)



print("二叉树的最大深度")
def maxDepth(root:TreeNode)->int:
    if not root:
        return 0
    return max(maxDepth(root.left),maxDepth(root.right))+1



print("判断是不是平衡二叉树"
      "二叉树的每个节点的左右子树的高度差的绝对值不超过 1，则二叉树是平衡二叉树。"
      "根据定义，一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，因此可以使用递归的方式判断二叉树是不是平衡二叉树，"
      "递归的顺序可以是自顶向下或者自底向上。"
      "1、每一个节点的左子结点和右子节点高度不能大于1"
      "2、每一个节点同时也是平衡二叉树")
def isBalanced(root:TreeNode)->bool:
    def height(node:TreeNode)->int:
        if not node:
            return 0
        return max(height(node.left),height(node.right))+1
    return abs(height(root.left)-height(root.right))<=1 and isBalanced(root.left) and isBalanced(root.right) if root else True


print("树的最小深度")
def minDepth(root:TreeNode)->int:
    if not root:
        return 0
    if not root.left:
        return minDepth(root.right)+1
    if not root.right:
        return minDepth(root.left)+1
    return min(minDepth(root.left),minDepth(root.right))+1


print("路径总和"
      "判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。"
      "如果存在，返回 true ；否则，返回 false 。")
def lujingzonghe(root:TreeNode,targetSum:int)->bool:
    def inner(node:TreeNode,target):
        if not node:
            return False
        target=target-node.val
        if node.left is None and node.right is None:
            return target==0
        return inner(node.left,target) or inner(node.right,target)
    return inner(root,targetSum)




print("给定一个非负整数n，返回杨辉三角的前n行")
def yanghuisanjiao001(numRows:int)->list[int]:
    source_list=[[1]*n for n in range(1,numRows+1)]
    if numRows<3:
        return source_list
    for i in range(2,numRows):
        for j in range(0,len(source_list[i])-1):
            source_list[i][j]=source_list[i-1][j-1]+source_list[i-1][j]
    return source_list


print("给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行")
def yanghuisanjiao002(numRows:int)->list[int]:
    source_list=[[1]*(n+1) for n in range(0,numRows+1)]
    if numRows<=1:
        return source_list[numRows]
    for i in range(2,numRows+1):
        for j in range(1,len(source_list[i])-1):
            source_list[i][j]=source_list[i-1][j-1]+source_list[i-1][j]
    return source_list[numRows]

print("买卖股票的最佳时机")
def maimaigupiao(prices:list[int])->int:
    profit=0
    min_price=prices[0]
    for p in prices:
        min_price=min(p,min_price)
        profit=max(profit,p-min_price)
    return profit


print("验证回文串"
      "如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串"
      "字母和数字都属于字母数字字符"
      "s = 'A man, a plan, a canal: Panama'")
def yanzhenghuiwenchuan(s:str)->bool:
    tem=[]
    for ss in s:
        if ss.isdigit():
            tem.append(ss)
        if ss.isalpha():
            tem.append(ss.lower())
    return tem==tem[::-1]


print("只出现一次的元素"
      "给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素")
def zhichuxainyiciyuansu(nums:list[int])->int:
    import collections
    counter=collections.Counter(nums)
    for k,v in counter.items():
        if v==1:
            return k


print("判断是不是环形链表")
def huanxinglianbiao(head:ListNode)->bool:
    if not head:
        return False
    fast=head
    slow=head
    while fast:
        if fast.next is None or fast.next.next is None:
            return False
        fast=fast.next.next
        slow=slow.next
        if fast==slow:
            return True


def qianxubianli(root:TreeNode)->list[int]:
    res=[]
    def dfs(node:TreeNode):
        if not node:
            return
        res.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return res
def zhongxubianli(root:TreeNode)->list[int]:
    res=[]
    def dfs(node:TreeNode):
        if not node:
            return
        dfs(node.left)
        res.append(node.val)
        dfs(node.right)
    dfs(root)
    return res
def houxubianli(root:TreeNode)->list[int]:
    res=[]
    def inner(node:TreeNode):
        if not node:
            return None
        inner(node.left)
        inner(node.right)
        res.append(node.val)
    inner(root)
    return res

print("返回相交链表的相交节点")
def xiangjiaojiedian(headA:ListNode,headB:ListNode)->ListNode:
    if not headA or not headB:
        return None
    current=headA
    tem_list=[]
    while current:
        tem_list.append(current)
        current=current.next
    current=headB
    while current:
        if current in tem_list:
            return current
        current=current.next
    return None


print("判断是不是多数元素"
      "给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素")
def duoshuyuansu(nums:list[int])->int:
    import collections
    counter=collections.Counter(nums)
    flag=len(nums)/2
    for k,v in counter.items():
        if v>flag:
            return k


print("判断是不是快乐数"
      "正整数各个位上的数的平方反复相加，看最终结果是否能等于1")
def kuaileshu(n:int)->bool:
    if n==1:
        return True
    cache_list=[]
    while True:
        tem= [int(i) for i in list(str(n))]
        res=0
        for t in tem:
            res=res+t**2
        if res==1:
            return True
        if res in cache_list:
            return False
        cache_list.append(res)
        n=res

def yichulianbiaoyuansu(head:ListNode,val:int)->ListNode:
    if not head:
        return None
    new_head=ListNode()
    new_head.next=head
    current=new_head
    while current.next:
        if current.next.val==val:
            current.next=current.next.next
        else:
            current=current.next
    return new_head.next


print("给定两个字符串，判定他们是否是同构字符串"
      "s = 'egg', t = 'add'")
def tonggouzifuchuan(s:str,t:str)->bool:
    if not s and not t:
        return True
    if not s or not t:
        return False
    if len(s) != len(t):
        return False
    s_list,t_list=list(s),list(t)
    s_map,t_map={},{}
    for k,v in zip(s_list,t_list):
        if k in s_map:
            if s_map[k]!=v:
                return False
        else:
            s_map[k]=v
        if v in t_map:
            if t_map[v]!=k:
                return False
        else:
            t_map[v]=k
    return True

print("反转链表")
def fanzhuanlianbiao(head:ListNode)->ListNode:
    if not head:
        return None
    pre=None
    current=head
    while current:
        tem=current.next
        current.next=pre
        pre=current
        current=tem
    return pre

print("存在重复元素 - 001"
      "简单的判断数组中是否有重复元素")
def chognfuyuansu01(nums:list[int])->bool:
    # return not len(set(nums))==len(nums)
    import collections
    counter_dict=dict(collections.Counter(nums))
    res_dict=dict(sorted(counter_dict,key=lambda item:item[1]))

    # 超时
    # for i in range(0,len(nums)):
    #     if i ==len(nums)-1:
    #         return False
    #     if nums[i] in nums[i+1:]:
    #         return True
    # return False


print("存在重复元素 - 002"
      "给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，"
      "满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false ")
def chongfuyuansu02(nums:list[int],k:int)->bool:
    val_key_dict={}
    for key,v in enumerate(nums):
        if v in val_key_dict:
            if abs(key-val_key_dict[v])<=k:
                return True
        val_key_dict[v]=key
    return False


print("完全二叉树的节点个数")
def count_node(root:TreeNode) ->int:
    if not root:
        return 0
    return count_node(root.left)+count_node(root.right)+1


print("反转二叉树")
def fanzhuanerchashu(root:TreeNode)->TreeNode:
    if not root:
        return None
    left=fanzhuanerchashu(root.left)
    right=fanzhuanerchashu(root.right)
    root.left=right
    root.right=left
    return root


print("2的幂")
def mi_2(n:int)->bool:
    if n<=0:
        return False
    if n==1:
        return True
    tem=1
    for i in range(0,n):
        tem=tem*2
        if tem==n:
            return True
        if tem>n:
            return False


print("回文链表")
def huiwenlianbiao(head:ListNode)->bool:
    if not head:
        return False
    current=head
    res=[]
    while current:
        res.append(current.val)
        current=current.next
    return res==res[::-1]

print("有效的字母异位词"
      "字母异位词 是通过重新排列不同单词或短语的字母而形成的单词或短语，通常只使用所有原始字母一次"
      "判断 t 是否是 s 的字母异位词  "
      "其实就是判断两个字符串长度是否相等  如果相等的话 两个字符串中每个字符出现的次数相等")
def yiweici(s:str,t:str)->bool:
    if len(s) != len(t):
        return False
    import collections
    s_counter=collections.Counter(s)
    t_counter=collections.Counter(t)
    mid_counter_1=s_counter-t_counter
    mid_counter_2=t_counter-s_counter
    return len(mid_counter_1)==0 and len(mid_counter_2)==0


print("各位相加"
      "给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果")
def geweixiangjia(num:int)->int:
    if num<10:
        return num
    while num>=10:
        tem = sum([int(n) for n in list(str(num))])
        if tem<10:
            return tem
        else:
            num=tem



print("判断是不是丑数")
def choushu(n:int)->bool:
    if n<=0:
        return False
    factors=[2,3,5]
    for f in factors:
        while n%f==0:
            n=n//f
    return True if n==1 else False

print("丢失的数字"
      "给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数")
def diushideshuzi(nums:list[int])->int:
    import collections
    counter=collections.Counter(nums)
    for i in range(0,len(nums)+1):
        if counter[i]==0:
            return i

print("第一个错误版本")
def isBadVersion(i:int)->bool:
    pass
def firstbadversion(n:int)->int:
    left_num,right_num=0,n
    while left_num <=right_num:
        mid=(left_num+right_num)//2
        if isBadVersion(mid):
            right_num=mid-1
        else:
            left_num=mid+1
    return left_num



print("移动0"
      "编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序")
test_num=[0,0,1,2,3]
test_num.remove(0)
print(test_num)
def yidong0(nums:list[int])->list[int]:
    count=nums.count(0)
    for c in range(0,count):
        nums.remove(0)
        nums.append(0)
    return nums



print("单词规律"
      "给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律"
      "pattern = 'abba', s = 'dog cat cat dog'")
def danciguilv(pattern:str,s:str)->bool:
    p_list=list(pattern)
    s_list=s.split()
    if len(p_list) !=len(s_list):
        return False
    p_map={}
    s_map={}
    for k,v in zip(p_list,s_list):
        if k in p_map:
            if p_map[k]!=v:
                return False
        else:
            p_map[k]=v
        if v in s_map:
            if s_map[v] !=k:
                return False
        else:
            s_map[v]=k
    return True

print("nim游戏")
def nim(n:int)->bool:
    return not n%4==0

print("3的幂")
def mi_3(n:int)->bool:
    if n<=0:
        return False
    if n==1:
        return True
    res=1
    for i in range(0,n):
        res=res*3
        if res==n:
            return True
        if res>n:
            return False


print("4的幂")
def mi_4(n:int)->bool:
    if n<=0:
        return False
    if n==1:
        return True
    res=1
    for i in range(0,n):
        res=res*4
        if res==n:
            return True
        if res>n:
            return False

print("不额外分配空间翻转字符串")
def fanzhuanstr(s:list[str])->list[str]:
    for i in range(0,len(s)//2):
        s[i],s[len(s)-i-1]=s[len(s)-i-1],s[i]
    return s

# str001="abcd"
# str001[0],str001[3]=str001[3],str001[0]
# print(str001)

print("反转字符串中的元音字母"
      "只有两个索引位置的值都是原因字母时才翻转")
def fanzhuanyuanyin(s:str)->str:
    left_index,right_index=0,len(s)-1
    yuanyin="aeiouAEIOU"
    str_list=list(s)
    while left_index<=right_index:
        if str_list[left_index] not in yuanyin:
            left_index=left_index+1
            continue
        if str_list[right_index] not in yuanyin:
            right_index=right_index-1
            continue
        str_list[left_index],str_list[right_index]=str_list[right_index],str_list[left_index]
        left_index=left_index+1
        right_index=right_index-1
    return "".join(str_list)




print("两个数组的交集"
      "每个元素只出现一次")
def intersect2(nums1:list[int],nums2:list[int])->list[int]:
    # import collections
    # return list(collections.Counter(nums1)&collections.Counter(nums2))
    return list(set(nums1).intersection(set(nums2)))


print("两个数组的交集"
      "给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。"
      "返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数"
      "一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。")
def intersect(nums1:list,nums2:list)->list[int]:
    import collections
    return list(((collections.Counter(nums1))&(collections.Counter(nums2))).elements())

print("有效的完全平方数")
def youxiaowanquanpingfangshu(num:int)->bool:
    if num<0:
        return False
    elif num<=1:
        return True
    else:
        for i in range(2,num+1):
            if i**2==num:
                return True
            if (i+1)**2>num:
                return False


print("二分法猜数字大小"
      "我会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字")
def guess(num:int)->bool:
    pass
def guessnumber(n:int)->int:
    left,right=1,n
    while left<=right:
        mid=(left+right)//2
        if guess(mid)==0:
            return mid
        elif guess(mid)>0:
            left=mid+1
        else:
            right=mid-1
    return -1



print("给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成"
      "magazine 中的每个字符只能在 ransomNote 中使用一次")
def canconstruct(ransomNote:str,magazine:str)->bool:
    import collections
    counter=collections.Counter(magazine)
    for s in ransomNote:
        counter[s]=counter[s]-1
        if counter[s]<0:
            return False
    return True


print("给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1")
def findfirstchar(s:str)->int:
    import collections
    counter=collections.Counter(s)
    for k,v in enumerate(s):
        if counter[v]==1:
            return k
    return -1


print("找不同找出随机添加的字符串 "
      "字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。"
      "请找出在 t 中被添加的字母。")
def finddiff(s:str,t:str)->str:
    import collections
    return list((collections.Counter(t))-(collections.Counter(s)))[0]


print("s" in "ss")
print("判断子序列 判断s是否是t的子序列"
      "字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。"
      "（例如，'ace'是'abcde'的一个子序列，而'aec'不是）")
def zixulie(s:str,t:str)->bool:
    if not s:
        return True
    current_index=0
    for tt in t:
        if tt==s[current_index]:
            current_index=current_index+1
            if current_index==len(s):
                return True
    return False



print("给定二叉树的根节点 root ，返回所有左叶子之和")
def zuoyezihe(root:TreeNode)->int:
    sum=0
    def inner(node:TreeNode)->int:
        if not node:
            return 0
        if node.left and node.left.left is None and node.left.right is None:
            nonlocal sum
            sum=sum+node.left.val
        inner(node.left)
        inner(node.right)
    inner(root)
    return sum




print("返回最长回文串")
def zuichanghuiwenchuan(s:str)->int:
    import collections
    counter=collections.Counter(s)
    res=0
    tem=0
    for k,v in counter.items():
        if v%2==0:
            res=res+v
        else:
            tem=1
            res=(v//2)*2+res
    return res+tem


print("返回数组中第三大的数")
def max_3(nums:list[int]) ->int:
    tem_list=sorted(list(set(nums)))
    if len(tem_list)<3:
        return tem_list[-1]
    else:
        return tem_list[-3]

print("字符串相加")
def strxiangjia(num1:str,num2:str)->str:
    list_1,list_2=list(num1),list(num2)
    index_1,index_2,jinwei=len(list_1)-1,len(list_2)-1,0
    res=""
    while index_1>=0 or index_2>=0:
        num1=int(list_1[index_1]) if index_1>=0 else 0
        num2=int(list_2[index_2]) if index_2>=0 else 0
        tem=num1+num2+jinwei
        res=str(tem%10)+res
        jinwei=tem//10
        index_1=index_1-1
        index_2=index_2-1
    return str(jinwei)+res if jinwei>0 else res


print("返回字符串中的单词数"
      "这里的单词指的是连续的不是空格的字符")
def dancishu(s:str)->int:
    return len(s.split())


print("排列硬币-返回完整阶梯行")
def wanzhengjieti(n:int)->int:
    if n==0 or n==1:
        return n
    tem=0
    for i in range(1,n+1):
        tem=tem+i
        if tem==n:
            return i
        if tem>n:
            return i-1


print("找到所有的从数组中消失的数字"
      "给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范"
      "围内但没有出现在 nums 中的数字，并以数组的形式返回结果")
def xiaoshishuzi(nums:list[int])->list[int]:
    import collections
    coubter=collections.Counter(nums)
    res=[]
    for i in range(1,len(nums)+1):
        if coubter[i]==0:
            res.append(i)
    return res

print("分发饼干")
def fenfabinggan(g:list[int],s:list[int])->int:
    child_index,cookie_index=0,0
    g.sort()
    s.sort()
    count_child=0
    while cookie_index<len(s) and child_index<len(g):
        if s[cookie_index]>=g[child_index]:
            cookie_index=cookie_index+1
            child_index=child_index+1
            count_child=count_child+1
        else:
            cookie_index=cookie_index+1
    return count_child



print("重复的子字符串"
      "给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成")
def chongfuzizifuchuan(s:str)->bool:
    for i in range(0,len(s)):
        if len(s)%len(s[0:i])==0:
            mid_str=s[::]
            tem=len(s)//len(s[0:i])
            for t in range(0,tem):
                mid_str=mid_str.replace(s[0:i],"")
            if len(mid_str)==0:
                return True
    return False